// 310.最小高度树
package Leetcode_Second_Brush;

import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class Solution310 {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (edges.length == 0)
            return new ArrayList<>() {
                {
                    add(0);
                }
            };

        Map<Integer, Integer> degree = new HashMap<>();
        Map<Integer, List<Integer>> paths = new HashMap<>();

        for (int i = 0; i < n; i++)
            degree.put(i, 0);

        for (int[] edge : edges) {
            degree.put(edge[0], degree.get(edge[0]) + 1);
            degree.put(edge[1], degree.get(edge[1]) + 1);
            paths.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(edge[1]);
            paths.computeIfAbsent(edge[1], k -> new ArrayList<>()).add(edge[0]);
        }

        Deque<Integer> queue = new LinkedList<>();
        for (int key : degree.keySet()) {
            if (degree.get(key) == 1)
                queue.offer(key);
        }

        List<Integer> layer = new ArrayList<>();
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int node = queue.poll();
                degree.put(node, degree.get(node) - 1);
                layer.add(node);
                List<Integer> path = paths.get(node);
                for (int p : path) {
                    degree.put(p, degree.get(p) - 1);
                    if (degree.get(p) == 1)
                        queue.offer(p);
                }
            }
            if (!queue.isEmpty())
                layer.clear();
        }

        return layer;
    }
}
